package leetcode_700;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *Game24_679_ 24点游戏 
 *describe:用集合深搜 限制搜索条件为搜两层 AC 10% 很好的题目	
 *2018年10月7日 下午12:13:06
 */
public class Game24_679_ {
	
	public static void main(String[] args) {
		Game24_679_ test=new Game24_679_();
		System.out.println(test.judgePoint24(new int[] {1,1,1,1}));
		System.out.println(0d/0d);
	}
	
	public boolean judgePoint24(int[] nums) {
        List<Double> list = new ArrayList<>();
        for (int i : nums) {
            list.add((double) i);
        }
        return dfs(list);
    }

    private boolean dfs(List<Double> list) {
    	//此处限制了深度搜索的条件 即只能搜索两次 因为超过两次size就为1了
        if (list.size() == 1) {
            if (Math.abs(list.get(0)- 24.0) < 0.001) {//有可能因为精度问题 为无穷接近24的数
                return true;
            }
            return false;
        }
        //相当于总共只有两轮
        for(int i = 0; i < list.size(); i++) {
            for(int j = i + 1; j < list.size(); j++) {
                for (double c : generatePossibleResults(list.get(i), list.get(j))) {
                	//c是所有产生组合的排列数
                    List<Double> nextRound = new ArrayList<>();
                    nextRound.add(c);
                    //此处才是算法的重点 因为在此之前 已经提取了i j的组合 那么就把除了i j的其他数单独放入集合中
                    for(int k = 0; k < list.size(); k++) {
                        if(k == j || k == i) continue;
                        nextRound.add(list.get(k));
                    }
                    if(dfs(nextRound)) return true;
                }
            }
        }
        return false;

    }

    /**
     * describe:穷举所有排列组合
     * 2018年10月7日 下午12:02:32
     */
    private List<Double> generatePossibleResults(double a, double b) {
        List<Double> res = new ArrayList<>();
        res.add(a + b);
        res.add(a - b);
        res.add(b - a);
        res.add(a * b);
        res.add(a / b);//0d/0d并不可能报异常
        res.add(b / a);
        return res;
    }
}
